{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Balls in a Box"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countBalls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #盒子中小球的最大数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你在一家生产小球的玩具厂工作，有 <code>n</code> 个小球，编号从 <code>lowLimit</code> 开始，到 <code>highLimit</code> 结束（包括 <code>lowLimit</code> 和 <code>highLimit</code> ，即 <code>n == highLimit - lowLimit + 1</code>）。另有无限数量的盒子，编号从 <code>1</code> 到 <code>infinity</code> 。</p>\n",
    "\n",
    "<p>你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 <code>321</code> 的小球应当放入编号 <code>3 + 2 + 1 = 6</code> 的盒子，而编号 <code>10</code> 的小球应当放入编号 <code>1 + 0 = 1</code> 的盒子。</p>\n",
    "\n",
    "<p>给你两个整数 <code>lowLimit</code> 和 <code>highLimit</code> ，返回放有最多小球的盒子中的小球数量<em>。</em>如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lowLimit = 1, highLimit = 10\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...\n",
    "小球数量：2 1 1 1 1 1 1 1 1 0  0  ...\n",
    "编号 1 的盒子放有最多小球，小球数量为 2 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lowLimit = 5, highLimit = 15\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...\n",
    "小球数量：1 1 1 1 2 2 1 1 1 0  0  ...\n",
    "编号 5 和 6 的盒子放有最多小球，每个盒子中的小球数量都是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lowLimit = 19, highLimit = 28\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "盒子编号：1 2 3 4 5 6 7 8 9 10 11 12 ...\n",
    "小球数量：0 1 1 1 1 1 1 1 1 2  0  0  ...\n",
    "编号 10 的盒子放有最多小球，小球数量为 2 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= lowLimit <= highLimit <= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-balls-in-a-box](https://leetcode.cn/problems/maximum-number-of-balls-in-a-box/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-balls-in-a-box](https://leetcode.cn/problems/maximum-number-of-balls-in-a-box/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n10', '5\\n15', '19\\n28']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        cn = [0] * 46\n",
    "        pre = sum([int(x) for x in str(lowLimit)])\n",
    "        cn[pre]+=1\n",
    "        for b in range(lowLimit+1, highLimit + 1):\n",
    "            pnum=b-1\n",
    "            while pnum%10==9:\n",
    "                pnum=pnum//10\n",
    "                pre-=9\n",
    "            pre+=1\n",
    "            cn[pre]+=1\n",
    "           \n",
    "        return max(cn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        count = Counter(sum(map(int, str(i))) for i in range(lowLimit, highLimit + 1))\n",
    "        return max(count.values())\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        dict = {}\n",
    "        _max = 0\n",
    "\n",
    "        def getSum(num):\n",
    "            res = 0\n",
    "            while num:\n",
    "                res += num % 10\n",
    "                num //= 10\n",
    "            return res\n",
    "\n",
    "        for n in range(lowLimit, highLimit + 1):\n",
    "            t = getSum(n)\n",
    "            dict[t] = dict.get(t,0)+1\n",
    "            _max = max(_max, dict[t])\n",
    "        return _max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        count = Counter(sum(map(int, str(i))) for i in range(lowLimit, highLimit + 1))\n",
    "        return max(count.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        dic = {}\n",
    "        for x in range(lowLimit, highLimit+1):\n",
    "            i, j = x, 0\n",
    "            while i>0:\n",
    "                i, j = i//10, j + i%10\n",
    "            dic[j] = dic.setdefault(j, 0) + 1\n",
    "        res = 0\n",
    "        for v in dic.values():\n",
    "            if v > res:\n",
    "                res = v\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        nums = [sum(int(digit) for digit in str(num)) for num in range(lowLimit,highLimit+1)]\n",
    "        return Counter(nums).most_common()[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, a: int, b: int) -> int:\n",
    "        a = str(a)\n",
    "        b = str(b)\n",
    "        n = len(b)\n",
    "        if len(a) < n:\n",
    "            a = \"0\" * (n - len(a)) + a\n",
    "        @cache\n",
    "        def d(i, s, la, lb, nm):\n",
    "            if s < 0: return 0\n",
    "            if i == n:\n",
    "                return int(nm and s == 0)\n",
    "            res = 0\n",
    "            l = int(a[i]) if la or not nm else 0\n",
    "            r = int(b[i]) if lb else 9\n",
    "            for j in range(l, r + 1):\n",
    "                res += d(i + 1, s - j, la and j == l, lb and j == r, nm or j > 0)\n",
    "            return res\n",
    "        return max(d(0, i, True, True, False) for i in range(46))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        c=Counter()\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            c[sum(int(j) for j in str(i))]+=1\n",
    "        return max(c.values())\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        count =Counter(sum(map(int,str(i))) for i in range(lowLimit,highLimit+1))\n",
    "        return max(count.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        cnt = Counter()\n",
    "        for i in range(lowLimit, highLimit + 1):\n",
    "            s = 0\n",
    "            while i:\n",
    "                s += i % 10\n",
    "                i //= 10\n",
    "            cnt[s] += 1\n",
    "        \n",
    "        return max(cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        count = Counter(sum(map(int, str(i))) for i in range(lowLimit, highLimit + 1))\n",
    "        return max(count.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        ans = {}\n",
    "        for num in range(lowLimit, highLimit+1):\n",
    "            if num >= 10:\n",
    "                tmp = 0\n",
    "                while num >= 10:\n",
    "                    tmp += num%10\n",
    "                    num //= 10\n",
    "                tmp += num\n",
    "                ans[tmp] = ans.get(tmp, 0) + 1\n",
    "            else:\n",
    "                ans[num] = ans.get(num, 0) + 1\n",
    "        \n",
    "        return max(ans.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        a=[0]*50\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            a[sum([int(j) for j in str(i)])]+=1\n",
    "        return max(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        def get_sum(num):\n",
    "            sum=0\n",
    "            while num>0:\n",
    "                t=num%10\n",
    "                sum+=t\n",
    "                num=num//10\n",
    "            return sum\n",
    "        n=highLimit-lowLimit+1\n",
    "        dic={}\n",
    "        for num in range(lowLimit,highLimit+1):\n",
    "            sum=get_sum(num)\n",
    "            dic[sum]=dic.get(sum,0)+1\n",
    "        print(dic)\n",
    "        return max([value for key,value in dic.items()])\n",
    "        # print(max([value for key, value in dic.items()]))\n",
    "        # while num>0:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        cnt = [0] * 50\n",
    "        for x in range(lowLimit, highLimit + 1):\n",
    "            y = 0\n",
    "            while x:\n",
    "                y += x % 10\n",
    "                x //= 10\n",
    "            cnt[y] += 1\n",
    "        return max(cnt)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        def get_sum(num):\n",
    "            s=list(str(num))\n",
    "            res=0\n",
    "            for i in s:\n",
    "                res+=int(i)\n",
    "            return res\n",
    "        count=0\n",
    "        dic={}\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            num=get_sum(i)\n",
    "            dic[num]=dic.get(num,0)+1\n",
    "        print(dic)\n",
    "        ans=[value for value in dic.values()]\n",
    "        return max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        count = Counter(sum(map(int, str(i))) for i in range(lowLimit, highLimit + 1))\n",
    "        return max(count.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        box = []\n",
    "        for i in range(45):\n",
    "            box.append(0)\n",
    "        # 制作盒子，最大盒子只能是（9+9+9+9+9)\n",
    "        box_max = 0  # 用于计算最大用到的盒子\n",
    "        for num in range(lowLimit, highLimit+1):\n",
    "            ind = 0  # 储存和运算\n",
    "            while True:\n",
    "                n = int(num) % 10\n",
    "                ind += n\n",
    "                num = num/10\n",
    "                if num < 1:\n",
    "                    break\n",
    "            box[ind - 1] += 1\n",
    "            if ind > box_max:\n",
    "                box_max = ind\n",
    "        # 搜索最多球的盒子\n",
    "        return max(box)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        countmap = {}\n",
    "        for i in range(lowLimit, highLimit + 1):\n",
    "            bitsum = sum(map(int, str(i)))\n",
    "            # countmap[bitsum]\n",
    "            if bitsum not in countmap:\n",
    "                countmap[bitsum] = 1\n",
    "            else:\n",
    "                countmap[bitsum] += 1\n",
    "        return max(countmap.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        def sum_num(num):\n",
    "            if num < 10:\n",
    "                return num\n",
    "            res = 0\n",
    "            while num > 0:\n",
    "                res += num % 10\n",
    "                num //= 10\n",
    "            return res\n",
    "        \n",
    "        hax = {}\n",
    "        m = 0\n",
    "        for i in range(lowLimit, highLimit+1):\n",
    "            temp = sum_num(i)\n",
    "            if temp not in hax:\n",
    "                hax[temp] = 0\n",
    "            hax[temp] += 1\n",
    "            if hax[temp] > m:\n",
    "                m = hax[temp]\n",
    "        \n",
    "        return m\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        ball = {} #key是盒子的编号，value是小球数量\n",
    "        for i in range(lowLimit, highLimit + 1):\n",
    "            temp = self.totalsum(i)\n",
    "            ball[temp] = ball.get(temp, 0) + 1\n",
    "        maxvalue = max(ball.values())\n",
    "        return maxvalue\n",
    "        # for k, v in ball.items():\n",
    "        #     if v == maxvalue:\n",
    "        #         return k\n",
    "\n",
    "    def totalsum(self, num):\n",
    "        sum = 0\n",
    "        while num > 0:\n",
    "            sum += num % 10\n",
    "            num = num // 10\n",
    "        return sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        cnt = [0] * 50\n",
    "        for x in range(lowLimit, highLimit + 1):\n",
    "            y = 0\n",
    "            while x:\n",
    "                y += x % 10\n",
    "                x //= 10\n",
    "            cnt[y] += 1\n",
    "        return max(cnt)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        cnt = [0] * 50\n",
    "        for x in range(lowLimit, highLimit + 1):\n",
    "            y = 0\n",
    "            while x:\n",
    "                y += x % 10\n",
    "                x //= 10\n",
    "            cnt[y] += 1\n",
    "        return max(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        res=0\n",
    "        dic={}\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            sum1=sum([int(d) for d in str(i)])\n",
    "            if sum1 not in dic:\n",
    "                dic[sum1]=1\n",
    "            else:\n",
    "                dic[sum1]+=1\n",
    "        for num in dic:\n",
    "            res=max(res,dic[num])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        cntDict = {}\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            sum = 0\n",
    "            for j in list(str(i)):\n",
    "                sum += int(j)\n",
    "            if sum in cntDict:\n",
    "                cntDict[sum] += 1\n",
    "            else:\n",
    "                cntDict[sum] = 1\n",
    "        return max(cntDict.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        def sum_num(num):\n",
    "            if num < 10:\n",
    "                return num\n",
    "            res = 0\n",
    "            while num > 0:\n",
    "                res += num % 10\n",
    "                num //= 10\n",
    "            return res\n",
    "        \n",
    "        hax = {}\n",
    "        for i in range(lowLimit, highLimit+1):\n",
    "            temp = sum_num(i)\n",
    "            if temp not in hax:\n",
    "                hax[temp] = 0\n",
    "            hax[temp] += 1\n",
    "        return max(hax.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        counter = Counter()\n",
    "        cnt = sum(map(int,list(str(lowLimit))))\n",
    "        counter[cnt]+=1\n",
    "        for i in range(lowLimit+1,highLimit+1):\n",
    "            if i % 100000 ==0:\n",
    "                cnt += 1 - 5*9\n",
    "            elif i % 10000 ==0:\n",
    "                cnt += 1-4*9\n",
    "            elif i % 1000 == 0:\n",
    "                cnt +=1-3*9\n",
    "            elif i % 100 == 0:\n",
    "                cnt +=1-2*9\n",
    "            elif i % 10 ==0:\n",
    "                cnt += 1-9\n",
    "            else:\n",
    "                cnt+=1\n",
    "            counter[cnt]+=1\n",
    "        \n",
    "        return max(counter.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "\n",
    "        def calc(num):\n",
    "            result = 0\n",
    "            while num > 0:\n",
    "                result += num % 10\n",
    "                num //= 10\n",
    "            return result\n",
    "        \n",
    "        result = 0\n",
    "        counter = defaultdict(int)\n",
    "        for i in range(lowLimit, highLimit+1):\n",
    "            t = calc(i)\n",
    "            counter[t] += 1\n",
    "            result = max(result, counter[t])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        def f(n):\n",
    "            ans=0\n",
    "            while n:\n",
    "                n,m=divmod(n,10)\n",
    "                ans+=m\n",
    "            return ans\n",
    "        \n",
    "        d=defaultdict(int)\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            d[f(i)]+=1\n",
    "        return max(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        box=[0]*46\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            x=0\n",
    "            while i>0:\n",
    "                x+=i%10\n",
    "                i//=10\n",
    "            box[x]+=1\n",
    "        return max(box)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        count = Counter(sum(map(int, str(i))) for i in range(lowLimit, highLimit + 1))\n",
    "        return max(count.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        box_count = {}\n",
    "        for num in range(lowLimit,highLimit + 1):\n",
    "            box_number = sum(int(digit) for digit in str(num))\n",
    "            box_count[box_number] = box_count.get(box_number, 0) + 1\n",
    "\n",
    "        max_count = max(box_count.values())\n",
    "        return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        count = Counter(sum(map(int, str(i))) for i in range(lowLimit, highLimit + 1))\n",
    "        return max(count.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        ans = 0\n",
    "        m = dict()\n",
    "        for i in range(lowLimit, highLimit + 1):\n",
    "            code = sum([int(c) for c in str(i)])\n",
    "            m[code] = m.get(code, 0) + 1\n",
    "            ans = max(ans, m[code])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        count = Counter(sum(map(int, str(i))) for i in range(lowLimit, highLimit + 1))\n",
    "        return max(count.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        res=0\n",
    "        dic={}\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            sum1=sum([int(d) for d in str(i)])\n",
    "            if sum1 not in dic:\n",
    "                dic[sum1]=1\n",
    "            else:\n",
    "                dic[sum1]+=1\n",
    "        for num in dic:\n",
    "            res=max(res,dic[num])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "\n",
    "        def helper(num: int) -> int:\n",
    "            res = 0\n",
    "            while num:\n",
    "                res += num % 10\n",
    "                num //= 10\n",
    "\n",
    "            return res\n",
    "\n",
    "        return collections.Counter(map(helper, range(lowLimit, highLimit+1))).most_common()[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, a: int, b: int) -> int:\n",
    "        a = str(a)\n",
    "        b = str(b)\n",
    "        n = len(b)\n",
    "        if len(a) < n:\n",
    "            a = \"0\" * (n - len(a)) + a\n",
    " \n",
    "        def d(i, s, la, lb, nm):\n",
    "            if s < 0: return 0\n",
    "            if i == n:\n",
    "                return int(nm and s == 0)\n",
    "            res = 0\n",
    "            l = int(a[i]) if la or not nm else 0\n",
    "            r = int(b[i]) if lb else 9\n",
    "            for j in range(l, r + 1):\n",
    "                res += d(i + 1, s - j, la and j == l, lb and j == r, nm or j > 0)\n",
    "            return res\n",
    "        return max(d(0, i, True, True, False) for i in range(46))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        dict1={}\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            temp=[int(j) for j in str(i)]\n",
    "            temp2=sum(temp)\n",
    "            if temp2 not in dict1:\n",
    "                dict1[temp2]=1\n",
    "            else:\n",
    "                dict1[temp2]+=1\n",
    "        return max(i for i in dict1.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, a: int, b: int) -> int:\n",
    "        a = str(a)\n",
    "        b = str(b)\n",
    "        n = len(b)\n",
    "        if len(a) < n:\n",
    "            a = \"0\" * (n - len(a)) + a\n",
    " \n",
    "        def d(i, s, la, lb, nm):\n",
    "            if s < 0: return 0\n",
    "            if i == n:\n",
    "                return int(nm and s == 0)\n",
    "            res = 0\n",
    "            l = int(a[i]) if la or not nm else 0\n",
    "            r = int(b[i]) if lb else 9\n",
    "            for j in range(l, r + 1):\n",
    "                res += d(i + 1, s - j, la and j == l, lb and j == r, nm or j > 0)\n",
    "            return res\n",
    "        return max(d(0, i, True, True, False) for i in range(46))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def ballNum(num):\n",
    "        sumVal = 0\n",
    "        for char in str(num):\n",
    "            sumVal += int(char)\n",
    "        return sumVal - 1\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        n = highLimit - lowLimit + 1\n",
    "        ans = [0] * highLimit\n",
    "        sumBall = n\n",
    "        maxVal = 0\n",
    "        for i in range(lowLimit, highLimit+1):\n",
    "            idx = self.ballNum(i)\n",
    "            ans[idx] += 1\n",
    "            maxVal = max(maxVal, ans[idx])\n",
    "            i += 1\n",
    "            sumBall -= 1\n",
    "        return maxVal\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        hash_value = [0] * 46\n",
    "        hash_nums = [0] * (highLimit + 1)\n",
    "        for i in range(highLimit + 1):\n",
    "            hash_nums[i] = hash_nums[i // 10] + i % 10\n",
    "        for i in range(lowLimit, highLimit + 1):\n",
    "            hash_value[hash_nums[i]] += 1\n",
    "        return max(hash_value)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, l: int, r: int) -> int:\n",
    "        \n",
    "        dp = [0] * (r+1)\n",
    "        for i in range(l, r+1):\n",
    "            dp[max(1, sum(map(int, list(str(i)))) )  ] += 1\n",
    "        # print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        low, high = str(lowLimit - 1), str(highLimit)\n",
    "        \n",
    "        def ballCount(s):\n",
    "            \n",
    "            def helper(pos, limit, selected, sum):\n",
    "                if pos == len(s):\n",
    "                    box[sum] += 1\n",
    "                    return \n",
    "                \n",
    "                if not selected:\n",
    "                    helper(pos + 1, 0, 0, 0)\n",
    "                \n",
    "                left = 1 if not selected else 0\n",
    "                right = 9 if not limit else int(s[pos])\n",
    "                for i in range(left, right + 1):\n",
    "                    helper(pos + 1, limit and i == right, 1, sum + i)\n",
    "            \n",
    "            box = [0] * 54\n",
    "            helper(0, 1, 0, 0)\n",
    "            return box\n",
    "        \n",
    "        low_box = ballCount(low)\n",
    "        high_box = ballCount(high)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(54):\n",
    "            res = max(res, high_box[i] - low_box[i])\n",
    "        \n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        hash_value = [0] * 46\n",
    "        hash_num = [0] * (highLimit + 1)\n",
    "        for i in range(1, highLimit + 1):\n",
    "            hash_num[i] = hash_num[i//10] + i % 10\n",
    "        for i in range(lowLimit, highLimit + 1):\n",
    "            hash_value[hash_num[i]] += 1\n",
    "        max_value = max(hash_value)\n",
    "        return max_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        i = lowLimit\n",
    "        dic ={}\n",
    "\n",
    "        while lowLimit <= i <= highLimit:\n",
    "            no = i\n",
    "            box = 0\n",
    "            while no > 0:\n",
    "                b = no % 10\n",
    "                no = no // 10\n",
    "                box += b\n",
    "            print(i,box)\n",
    "            dic[box]=dic.get(box,0)+1\n",
    "            i = i+1    \n",
    "\n",
    "        max = 0\n",
    "        for k, v in dic.items():\n",
    "            if v > max:\n",
    "                max = v\n",
    "        return max\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        # dic={}\n",
    "        # for i in range(lowLimit,highLimit+1):\n",
    "        #     x=str(i)\n",
    "        #     n=0\n",
    "        #     for j in range(len(x)):\n",
    "        #         n+=int(x[j])\n",
    "        #     if n not in dic:\n",
    "        #         dic[n]=1\n",
    "        #     else:\n",
    "        #         dic[n]+=1\n",
    "        # # print(dic)\n",
    "        # return max(dic.values())\n",
    "\n",
    "        hash_value = [0] * 46   \n",
    "        hash_num = [0] * (highLimit + 1) \n",
    "        print('1',hash_value,hash_num)\n",
    "        for i in range(1,highLimit + 1):\n",
    "            hash_num[i] = hash_num[i//10] + i % 10\n",
    "        print('2',hash_num)\n",
    "        for i in range(lowLimit, highLimit + 1):\n",
    "            hash_value[hash_num[i]] += 1\n",
    "        print('3',hash_value)\n",
    "        return max(hash_value)\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        def break_nums(num: int) -> List:\n",
    "            digits = []\n",
    "            while(num):\n",
    "                digit = num % 10\n",
    "                num = num // 10\n",
    "                digits.append(digit)\n",
    "            return digits\n",
    "        \n",
    "        box = [0] * highLimit\n",
    "        for i in range(lowLimit, highLimit+1):\n",
    "            box[sum(break_nums(i))-1] += 1\n",
    "\n",
    "        return max(box)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        b = []\n",
    "        for i in range(lowLimit, highLimit + 1):\n",
    "            a = sum(list(map(int, list(str(i)))))\n",
    "            b.append(a)\n",
    "        print(b)\n",
    "        c=sorted(list(Counter(b).items()),key=lambda x:x[1],reverse=True)\n",
    "        return(c[0][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        result = [0] * (highLimit+1)\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            temp = 0\n",
    "            for j in str(i):\n",
    "                temp += int(j)\n",
    "            print(temp)\n",
    "            result[temp] += 1\n",
    "        return max(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        box = [0] * (highLimit + 1)\n",
    "        for ball in range(lowLimit, highLimit + 1):\n",
    "            idx = sum(int(i) for i in str(ball))\n",
    "            print(idx)\n",
    "            box[idx] += 1\n",
    "        return max(box)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        box_num = []\n",
    "        hash_t = {}\n",
    "        for i in range(lowLimit,highLimit + 1):\n",
    "            num = 0\n",
    "            while i > 0:\n",
    "                num += i % 10\n",
    "                i //= 10\n",
    "            box_num.append(num)\n",
    "        for i in box_num:\n",
    "            hash_t[i] = hash_t.get(i,0) + 1\n",
    "        return max(hash_t.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "@lru_cache(None)\n",
    "def cal(upper: int, target: int) -> int:\n",
    "    @lru_cache(None)\n",
    "    def dfs(pos: int, hasLeadingZero: int, isLimit: bool, curSum: int) -> int:\n",
    "        \"\"\"当前在第pos位，hasLeadingZero表示有前导0，isLimit表示是否贴合上界\"\"\"\n",
    "        if pos == len(nums):\n",
    "            return 1 if curSum == target else 0\n",
    "\n",
    "        res = 0\n",
    "        up = nums[pos] if isLimit else 9\n",
    "        for cur in range(up + 1):\n",
    "            if hasLeadingZero and cur == 0:\n",
    "                res += dfs(pos + 1, True, (isLimit and cur == up), curSum)\n",
    "            else:\n",
    "                res += dfs(pos + 1, False, (isLimit and cur == up), curSum + cur)\n",
    "        return res\n",
    "\n",
    "    nums = list(map(int, str(upper)))\n",
    "    return dfs(0, True, True, 0)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        return max(\n",
    "            cal(highLimit, target) - cal(lowLimit - 1, target)\n",
    "            for target in range(1, 9 * len(str(highLimit)) + 1)\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        a=[]\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            everyhe=self.he(i)\n",
    "            a.append(everyhe)\n",
    "        cnt=Counter(a)\n",
    "        return max(cnt.values())\n",
    "    def he(self,x):\n",
    "        x=list(str(x))\n",
    "        return sum([int(i) for i in x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        tmp=[sum(list(map(int,str(i)))) for i in range(lowLimit, highLimit+1)]\n",
    "        return Counter(tmp).most_common()[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        ans = [0] * (10 ** 5)\n",
    "        for i in range(lowLimit,highLimit+1):\n",
    "            sum_num = 0\n",
    "            for j in str(i):\n",
    "                sum_num += int(j)\n",
    "            ans[sum_num] += 1\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        l = []\n",
    "        for num in range(lowLimit, highLimit+1):\n",
    "            l.append(sum([int(_) for _ in list(str(num))]))\n",
    "        return sorted(Counter(l).values())[::-1][0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        return max(collections.Counter([sum(int(c) for c in str(v)) for v in range(lowLimit, highLimit+1)]).values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        res=[0 for _ in range(highLimit+1)]        \n",
    "        def sn(n):            \n",
    "            return sum([int(i) for i in str(n)])        \n",
    "        for i in range(lowLimit,highLimit+1):            \n",
    "            res[sn(i)]+=1            \n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        box_num = []\n",
    "        hash_t = {}\n",
    "        for i in range(lowLimit,highLimit + 1):\n",
    "            num = 0\n",
    "            while i > 0:\n",
    "                num += i % 10\n",
    "                i //= 10\n",
    "            box_num.append(num)\n",
    "        for i in box_num:\n",
    "            hash_t[i] = hash_t.get(i,0) + 1\n",
    "        return max(hash_t.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        res=[0 for _ in range(highLimit+1)]        \n",
    "        def sn(n):\n",
    "            r=[int(i) for i in str(n)]\n",
    "            return sum(r)        \n",
    "        for i in range(lowLimit,highLimit+1):            \n",
    "            res[sn(i)]+=1            \n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        def f(x):\n",
    "            def check(n,x):\n",
    "                s=str(n)\n",
    "                @cache\n",
    "                def dfs(i,is_limit,is_num,cnt):  \n",
    "                    if i==len(s):\n",
    "                        return int(cnt==x)\n",
    "                    res=0\n",
    "                    if not is_num:\n",
    "                        res=dfs(i+1,False,False,0) \n",
    "                    l=0 if is_num else 1\n",
    "                    r=int(s[i]) if is_limit else 9\n",
    "                    for d in range(l,r+1):\n",
    "                        if cnt+d<=x:\n",
    "                            res+=dfs(i+1,is_limit and d==r,True,cnt+d)\n",
    "                    return res\n",
    "                return dfs(0,True,False,0)\n",
    "            return check(highLimit,x)-check(lowLimit-1,x)\n",
    "        return max(f(i) for i in range(1,50))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        res=[0 for _ in range(highLimit+1)]        \n",
    "        def sn(n): return sum([int(i) for i in str(n)])        \n",
    "        for i in range(lowLimit,highLimit+1):            \n",
    "            res[sn(i)]+=1            \n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        box_num = []\n",
    "        hash_t = {}\n",
    "        for i in range(lowLimit,highLimit + 1):\n",
    "            num = 0\n",
    "            while i > 0:\n",
    "                num += i % 10\n",
    "                i //= 10\n",
    "            box_num.append(num)\n",
    "        cnt_list = [0 for i in range(100)]\n",
    "        for i in box_num:\n",
    "            cnt_list[i] += 1\n",
    "        return max(cnt_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "\n",
    "        v = Counter( list( sum( map( int, str(i))) for i in range(lowLimit, highLimit+1) )) \n",
    "        # print(\"v: \", v)\n",
    "\n",
    "        return max(v.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBalls(self, lowLimit: int, highLimit: int) -> int:\n",
    "        box_num = []\n",
    "        hash_t = {}\n",
    "        for i in range(lowLimit,highLimit + 1):\n",
    "            num = 0\n",
    "            while i > 0:\n",
    "                num += i % 10\n",
    "                i //= 10\n",
    "            box_num.append(num)\n",
    "        for i in box_num:\n",
    "            hash_t[i] = hash_t.get(i,0) + 1\n",
    "        return max(hash_t.values())\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
